Dmitry Lelyushenko sinh năm 1901 ở Rostov Oblast. Ông là người Ukraina.[1] Ở tuổi 17, Lelyushenko tham gia lực lượng kỵ binh của Semyon Budyonny trong lực lượng Bolshevik trong Nội chiến Nga. Được chọn làm sĩ quan sau chiến tranh, ông hoàn thành khóa học quân sự vào năm 1933 tại Học viện Quân sự MV Frunze và chuyển đến một lữ đoàn cơ giới trước khi thăng cấp lên cấp thiếu tá và chỉ huy một trung đoàn xe tăng ở Quân khu Moskva.